package algorithm_demo.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 面试题 08.07. 无重复字符串的排列组合
 * https://leetcode.cn/problems/permutation-i-lcci/
 * @author Api
 * @date 2023/5/3 11:36
 */
public class Problem_08_07_PermutationILCCI {
    public static List<String> list = new ArrayList<>();
    public String[] permutation(String S) {
        permutation(S.toCharArray(), 0);
        String[] res = new String[list.size()];
        for(int i = 0; i<res.length; i++){
            res[i] = list.get(i);
        }
        return res;
    }

    public static void permutation(char[] arr, int first){
        if (first == arr.length - 1){
            list.add(new String(arr));
            return;
        }
        for(int i = first; i< arr.length; i++){
            swap(arr, first, i);
            permutation(arr, first+1);
            swap(arr, first, i);
        }
    }

    public static void swap(char[] arr, int i, int j){
        char tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
